/*
 * @lc app=leetcode.cn id=773 lang=typescript
 *
 * [773] 滑动谜题
 */

// @lc code=start

class Data {
  constructor(public status: string, public step: number) {
    this.status = status;
    this.step = step;
  }
}

function slidingPuzzle(board: number[][]): number {
  const dirs = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];
  const endStatus = '123450';
  const initStatus = board.toString().split(',').join('');

  const getNexts = (status: string): string[] => {
    const arr = status.split('');
    const idx = arr.indexOf('0');
    // 每次0移动后的下一个状态
    const result = [];
    for (let i = 0; i < dirs.length; i++) {
      // 一维坐标转二维坐标
      let x = dirs[i][0] + ((idx / 3) >> 0);
      let y = dirs[i][1] + (idx % 3);
      if (x < 0 || x >= 2) continue;
      if (y < 0 || y >= 3) continue;
      // 二维坐标转一维坐标
      let nextIdx = x * 3 + y;
      // 交换得到新的状态
      [arr[idx], arr[nextIdx]] = [arr[nextIdx], arr[idx]];
      // 存入结果
      result.push(arr.join(''));
      // 还原，方便下一次更新状态
      [arr[idx], arr[nextIdx]] = [arr[nextIdx], arr[idx]];
    }
    return result;
  };

  const visited: Set<string> = new Set();
  const queue: Data[] = [];
  queue.push(new Data(initStatus, 0));
  visited.add(initStatus);

  while (queue.length) {
    const data = queue.shift();
    if (data.status === endStatus) return data.step;
    const nexts = getNexts(data.status);
    for (let next of nexts) {
      if (visited.has(next)) continue;
      queue.push(new Data(next, data.step + 1));
      visited.add(next);
    }
  }

  return -1;
}
// @lc code=end
